//#define  _CRT_SECURE_NO_WARNINGS 1
//#include <assert.h>
//#include <iostream>
//
//
//namespace ghs
//{
//	template<class T>
//	struct ListNode
//	{
//		ListNode<T>* _prev;
//		ListNode<T>* _next;
//		T _data;
//
//		ListNode(const T& x = T())
//			:_prev(nullptr),
//			_next(nullptr),
//			_data(x)
//		{
//		}
//	};
//
//	template<class T>
//	struct ListIterator
//	{
//		typedef ListNode<T> Node;
//		typedef ListIterator<T> Self;
//
//		ListIterator(Node* node)
//			:_node(node)
//		{}
//
//		//it1 != it2
//		bool operator!=(const Self& it)
//		{
//			return _node != it._node;
//		}
//
//		bool operator==(const Self& it)
//		{
//			return _node == it._node;
//		}
//		//*it
//		T& operator*()
//		{
//			return _node->_data;
//		}
//
//		//++it
//		Self& operator++()
//		{
//			_node = _node->_next;
//			return *this;
//		}
//		//it++ 
//		Self operator++(int)
//		{
//			Self tmp(*this);
//			_node = _node->_next;
//			return tmp;
//		}
//
//		//--it
//		Self& operator--()
//		{
//			_node = _node->_prev;
//			return *this;
//		}
//		//it-- 
//		Self operator--(int)
//		{
//			Self tmp(*this);
//			_node = _node->_prev;
//			return tmp;
//		}
//
//		Node* _node;
//	};
//
//	template<class T>
//	class List
//	{
//		typedef ListNode<T> Node;
//	public:
//		typedef ListIterator<T> iterator;
//
//		List()
//		{
//			_head = new Node;
//			_head->_next = _head;
//			_head->_prev = _head;
//		}
//
//		iterator begin()
//		{
//			return iterator(_head->_next);
//		}
//
//		iterator end()
//		{
//			return iterator(_head);
//		}
//
//		/*void push_back(const T& x)
//		{
//			Node* newnode = new Node(x);
//			Node* tail = _head->_prev;
//
//			tail->_next = newnode;
//			newnode->_prev = tail;
//			newnode->_next = _head;
//			_head->_prev = newnode;
//		}*/
//		void push_back(const T& x)
//		{
//			insert(end(), x);
//		}
//
//		void push_front(const T& x)
//		{
//			insert(begin(), x);
//		}
//
//		void pop_back()
//		{
//			erase(--end());
//		}
//
//		void pop_front()
//		{
//			erase(begin());
//		}
//
//
//		void insert(iterator pos, const T& val)
//		{
//			Node* cur = pos._node;
//			Node* prev = cur->_prev;
//			Node* newnode = new Node(val);
//			// prev newnode cur
//			prev->_next = newnode;
//			newnode->_prev = prev;
//			newnode->_next = cur;
//			cur->_prev = newnode;
//		}
//
//		iterator erase(iterator pos)
//		{
//			Node* cur = pos._node;
//			Node* prev = cur->_prev;
//			Node* next = cur->_next;
//
//			prev->_next = next;
//			next->_prev = prev;
//			delete cur;
//
//			return iterator(next);
//		}
//	private:
//		Node* _head;
//	};
//
//	
//
//	void test_list()
//	{
//		List<int> lt;
//		lt.push_back(1);
//		lt.push_back(2);
//		lt.push_back(3);
//		lt.push_back(4);
//
//		List<int>::iterator it = lt.begin();
//		while (it != lt.end())
//		{
//			std::cout << *it << " ";
//			++it;
//		}
//		std::cout << std::endl;
//
//		lt.push_front(10);
//		lt.push_front(20);
//		lt.push_front(30);
//
//		it = lt.begin();
//		while (it != lt.end())
//		{
//			std::cout << *it << " ";
//			++it;
//		}
//		std::cout << std::endl;
//
//		lt.push_back(10);
//		lt.push_back(20);
//		lt.push_back(30);
//
//		it = lt.begin();
//		while (it != lt.end())
//		{
//			std::cout << *it << " ";
//			++it;
//		}
//		std::cout << std::endl;
//
//		lt.pop_back();
//
//		for (auto e : lt)
//		{
//			std::cout << e << " ";
//		}
//		std::cout << std::endl;
//
//		lt.pop_front();
//		for (auto e : lt)
//		{
//			std::cout << e << " ";
//		}
//		std::cout << std::endl;
//	}
//}